\documentclass[a4paper, 12pt, titlepage]{article}
\usepackage[cm]{fullpage}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{times}
\usepackage{cite}
\usepackage{xcolor}
\usepackage[pdftex]{graphicx}
\usepackage{indentfirst}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{amsmath}
\newtheorem{ru_def}{Определение}
\usepackage[pdftex, unicode]{hyperref}
 \hypersetup{
    pdfnewwindow=true,      % links in new window
    colorlinks=true,        % false: boxed links; true: colored links
    linkcolor=black,        % color of internal links
    urlcolor=blue,          % color of external links
    citecolor=black
}

%\usepackage[margin=10pt,font=small,labelfont=bf]{caption}
\usepackage{caption2}
\renewcommand{\captionlabeldelim }{.}

%\renewcommand{\thesection}{\arabic{section}.}

\graphicspath{{pics/}}

\clubpenalty=10000
\widowpenalty=10000

\begin{document}
\begin{titlepage}
\begin{center}
Санкт-Петербургский национальный исследовательский университет\\
информационных технологий, механики и оптики\\
Факультет информационных технологий и программирования\\
Кафедра <<Компьютерные Технологии>>

\vspace{10em}
\large Н. С. Буланова (группа 4539), А. С. Буздалова (группа 5538)\\
\vspace{3em}
\Large Отчет о выполнении задания по теории информации\\
<<Получение оценок информационных характеристик источника>>\\
\vspace{3em}
\large Вариант 16\\

\vfill
\normalsize Санкт-Петербург\\
2012
\end{center}
\end{titlepage}

\sloppy
\section{Формулировка задачи исследования и исходные данные}
\subsection{Формулировка задачи}
	\begin{itemize}
		\item Построить эмпирическое распределение вероятностей на последовательностях длины $n = 1, 2, 3, 4.$ Рассмотреть «скользящие» блоки, т.е. в последовательности  длины $N$ наблюдается $N - n + 1$ блоков длины $n$. 
		\item Оценить энтропию на букву источника $H_n(X)$, приписав нулевые вероятности последовательностям букв, которые не встретились в файле при $n = 1, 2, 3, 4.$ 
		\item Оценить энтропию на букву источника $H_n(X)$, приписывая вероятности порядка $\frac{1}{N^n}$ последовательностям букв, которые не встретились в файле и соответственно нормируя вероятности остальных последовательностей, при $n = 1, 2, 3, 4.$
		\item Применить к заданной последовательности один из известных архиваторов (например, RAR, pkzip). Сопоставить результаты с оценками энтропии на сообщение.
	\end{itemize}
\subsection{Исходные данные}
Файл данных для изучения статистических свойств источника -- {\tt asyoulik.txt} -- текст комедии Уильяма Шекспира "As you like it" на английском языке.
\section{Метод решения}
%Расчетные формулы, комментированные листинги программ, пояснения.
Будем использовать следующие обозначения:
\begin{itemize}
	\item $n$ -- длина последовательности;
	\item $LEN$ -- число символов в файле;
	\item $ALF$ -- мощность алфавита;
	\item $K$ -- количество последовательностей определенной длины, встретившихся в файле;
	\item $b = LEN - n + 1$ -- количество блоков;
	\item $a$ -- число появлений последовательности в файле;
	\item $p_0$ -- вероятность последовательностей, которые не встретились в файле;
	\item $p_1$ -- вероятность последовательности, встретившейся в файле.
\end{itemize}

Вероятность последовательности оценим как $p_1 = \frac{a}{b}$. Припишем нулевые вероятности последовательностям, которые не встретились в файле. Тогда $$H^n = - \sum{p_1\log{p_1}}.$$ Оценим $H_n$ \cite{info-theory}: $$H_n \leq \frac{H^n}{n}.$$

Теперь припишем последовательностям, не встретившимся в файле, вероятности $p_0 = \frac{1}{LEN^n}.$ Число таких последовательностей составляет $ALF^n - K$. Произведем нормировку вероятностей остальных последовательностей: $$p_1 = \frac{a}{b(1 + \frac{ALF^n - K}{LEN^n})}.$$ 
Тогда $$H^n = -\sum{p_1\log{p_1}} + (-(ALF^n - K)p_0\log{p_0}),$$
$$H_n \leq \frac{H^n}{n}.$$

Построение эмпирического распределения вероятностей и оценка энтропии на букву источника были произведены с помощью программ, написанных на языках Java и C++. Листинги программ находятся в приложении.

\section{Результаты вычислений}
%Результаты вычислений по шагам выполнения задания.

Результаты построения распределения вероятностей последовательностей представлены на рис. \ref{n1}, \ref{n2-4}. Последовательности пронумерованы в порядке, соответствующем первому появлению последовательности в файле. 

\begin{figure}[tbh!]
\centering
\includegraphics[width=\textwidth]{n1.png}
\caption{Распределение вероятностей для n = 1}
\label{n1}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=\textwidth]{n2-4.png}
\caption{Распределение вероятностей для n = 2, 3, 4}
\label{n2-4}
\end{figure}

\newpage
Результаты вычисления энтропии на букву источника для различных значений $n$ представлены в таблице. Рассмотрены два варианта задания вероятности последовательностей, не встретившихся в файле. Из таблицы видно, что с ростом $n$ значение энтропии уменьшается в обоих случаях. Можно предположить, что для текстов на естественных языках уровень неосведомленности о том, какое из сообщений будет порождено источником, уменьшается при увеличении длины рассматриваемой последовательности.

\begin{table}[tbh!]
\begin{center}
\caption{Результаты вычисления энтропии} \label{table}
\begin{tabular}{|l|l|l|l|l|}
\hline
$n$ & $H_n, p_0 = 0$ & $H_n, p_0 = \frac{1}{LEN^n}$ & $\Delta H_n$ & $\frac{1}{LEN^n}$\\ \hline
1 & 4.80808840430875 & 4.82847179545035 & $2.04 * 10^{-2}$ & $7.99 * 10^{-6}$ \\ \hline
2 & 4.11286245705368 & 4.11291812226955 & $5.57 * 10^{-5}$ & $6.38 * 10^{-11}$ \\ \hline
3 & 3.58795651434915 & 3.58795663256468 & $1.18 * 10^{-7}$ & $5.10 * 10^{-16}$ \\ \hline
4 & 3.16487639071067 & 3.16487639095849 & $2.48 * 10^{-10}$& $4.07 * 10^{-21}$\\ \hline
\end{tabular}
\end{center}
\end{table}

Также можно видеть, что с ростом $n$ энтропии в случае с нулевой вероятностью не встретившихся последовательностей $p_0 = 0$ и в случае с вероятностью $p_0 = \frac{1}{LEN^n}$ практически совпадают. Например, для $n = 4$ энтропии отличаются лишь в десятом знаке после запятой. Это можно объяснить тем, что во втором случае вероятность $p_0$ также близка к нулю.

\section{Сравнение с архиваторами}
%Сравнение теоретически достижимых характеристик сжатия с эффективностью используемых на практике архиваторов.
Энтропию на букву источника можно рассматривать как среднее количество информации, необходимое для хранения одного символа. Оценим среднее количество информации, необходимое для хранения одного символа после сжатия файла с использованием архиватора. Пусть $s$ -- число кодируемых символов, $size_0$ -- число бит, необходимое для хранения исходного файла, $size_1$ -- число бит, необходимое для хранения сжатого файла. Тогда
$$ s * \log_2{(ALF)} \text{ bit} = size_0, $$
$$ s * x\text{ bit} = size_1.$$
Получаем, что количество информации, необходимое для хранения одного символа файла после сжатия, в среднем составляет 
$$x = \frac{\log_2{(ALF)} * size_1}{size_0},$$ 
где в условиях данной задачи $ALF = 256$, $size_0 = 125179 \text{ byte}$. В таблице \ref{arch} показаны результаты сжатия исходного файла с помощью различных архиваторов.

\begin{table}[tbh!]
\begin{center}
\caption{Результаты применения архиваторов} \label{arch}
\begin{tabular}{|l|l|l|}
\hline
Тип архиватора & $size_1, \text{ byte}$ & $x$ \\ \hline
bz2 & 39560 & $2,5282$\\ \hline
7z & 44586 & $2,8494$ \\ \hline
rar & 46985 & $ 3,0027$ \\ \hline
gz & 47109 & $3,0107$ \\ \hline
zip & 47236 & $3,0188$ \\ \hline
\end{tabular}
\end{center}
\end{table}

Из сравнительного анализа таблиц \ref{table}, \ref{arch} можно заключить, что эффективность сжатия, производимого с использованием архиваторов, существенно выше теоретически достижимых характеристик сжатия, оцененных с помощью энтропии на букву источника $H_n$ при $n = 1, 2, 3, 4.$ Вероятно, алгоритмы, использующиеся в архиваторах, достаточно сложны, и для верной теоретической оценки характеристик сжатия следует учитывать их особенности.

\section{Выводы}

Использование информации о нескольких предыдущих символах позволяет уменьшить энтропию на букву источника, однако его недостаточно для достижения характеристик сжатия, получаемых с помощью алгоритмов, применяемых в реально существующих архиваторах.

\begin{thebibliography}{99}
\bibitem{info-theory} Кудряшов Б. Д. Теория информации: Учебник для вузов. -- СПб.: Питер, 2009. -- 320 с.
\end{thebibliography}

\newpage
\section*{Приложение 1. Построение эмпирического распределения вероятностей}

\begin{lstlisting}
public class DistributionCalculator {
	
	public static Map<String, Integer> 
	calculate(Reader r, int n, int length) 
	throws IOException {

//Read file

		StringBuilder b = new StringBuilder();		
		int j = 0;
		while(j <= length && r.ready()) {
			b.append((char) r.read());
			j++;
		}
		String s = b.toString();
		
//Calculate number of equal blocks

		Map<String, Integer> map = 
			new HashMap<String, Integer>();
		for (int i = 0; i < s.length() - n; i++) {
			String key = s.substring(i, i + n);
			if (!map.containsKey(key)) {
				map.put(key, 1);
			} else {
				map.put(key, map.get(key) + 1);
			}
		}
		return map;
	}
	
//Write number of equal blocks to output file
	
	private static void 
	writeOutput(Map<String, Integer> map, Writer w) 
	throws IOException {
		w.append(String.format("%d\n", 
			map.values().size()));
		for (Integer i : map.values()) {
			w.append(String.format("%d\n", i));
		}
	}
	
//Run the program
	
	public static void main(String[] args) 
	throws IOException {
		final int length = 125179;		
		for (int i = 1; i <= 4; i++) {
			Reader r = new BufferedReader(
				new FileReader("../../asyoulik.txt"));
			Writer w = new FileWriter(
				String.format("../../probabs-%d.txt", i));
			writeOutput(calculate(r, i, length), w);
			w.close();
			r.close();
		}
	}
}
\end{lstlisting}

\section*{Приложение 2. Оценка энтропии на букву источника}

\begin{lstlisting}
#include <iostream>
#include <cmath>

using namespace std;

double log2(double a)
{
    return log(a)/log((double)2); 
}

int main()
{
    int LEN = 125179;
    int ALF = 256;
    int n = 1;
    int k, a, b;
    double sum = 0;                                   //H^n
    double p, x;

    freopen("probabs-1.txt", "r", stdin);
    freopen("out1.txt", "w", stdout);

    cin >> k;

    x = pow((double)ALF,n);
    x = 1 + (double)(x - k)/pow((double)LEN, n);      //normalization
    b = LEN - n + 1;

    for (int i = 0; i < k; i++)                       //summ(-p*log(p))
    {
        cin >> a;
        p = (double)a/b;
        p = (double)p/x;
        sum += -p*log2(p);        
    }
    x = pow((double)LEN,n);
    p = (double)1/x;
    sum += -(pow((double)ALF,n) - k)*p*log2(p);
    double e = (double)sum/n;                         //Hn
    cout.precision(15);
    cout << e;

    return 0;
}
\end{lstlisting}

\end{document} 